package mytest;

import java.util.Stack;

public class TreeTest2 {

	static class Node
	{
		Node left,right;
		int data;
		public Node(int data)
		{
			this.data=data;
		}
	}
	
	
	static Node solve(Node root)
	{
		int max=Integer.MIN_VALUE;
		Node result=null;
		Stack<Node> stack=new Stack<Node>();
		Stack<Integer> flag=new Stack<Integer>();
		Node p=root;
		while(p!=null||!stack.empty())
		{
			if(p!=null)
			{
				stack.push(p);
				flag.push(0);
				p=p.left;
			}else{
				while(!flag.empty()&&flag.peek()==1)
				{
					Node n=stack.pop();
					flag.pop();
					if(n.data>max)
					{
						result=n;
						max=n.data;
					}
					if(!stack.empty())
					{
						stack.peek().data+=n.data;
					}
				}
				
				if(!flag.empty())
				{
					flag.pop();
					flag.push(1);
					p=stack.peek().right;
				}
			}
		}
		return result;
	}
	
	static Node result=null;
	static int max=Integer.MIN_VALUE;
	static int solve2(Node root)
	{
		if(root==null)return 0;
		int p=root.data+solve2(root.left)+solve2(root.right);
		if(p>max)
		{
			max=p;
			result=root;
		}
		return p;
	}
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception {

		Node root=new Node(-1);
		root.left=new Node(-2);
		root.left.left=new Node(5);
		root.left.right=new Node(4);
		
		root.right=new Node(-3);
		root.right.left=new Node(7);
		root.right.right=new Node(8);
		
		//System.out.println(solve(root).data);
		
		solve2(root);
		System.out.println(max);
	}

}
